package com.atguigu.search;

import sun.java2d.pipe.RegionIterator;

import java.util.Arrays;

/**
 * @author durant
 * @create 2021-11-16 11:08
 */
public class InsertValueSearch {
    public static void main(String[] args) {
        int[] arr =new int[100];
        for (int i = 0; i < 100; i++) {
            arr[i] = i*2;
        }
        System.out.println(Arrays.toString(arr));
        int index =insertValueSearch(arr , 6, 99,9);
        System.out.println(index);

    }

    //


    /**
     *@param , left, right, findval]
     *@return int
     */
    private static int insertValueSearch(int[] arr,int left , int right ,int findval) {
        System.out.println("halo");
        if (left > right || findval < arr[0] || findval >arr[arr.length-1]){// 当满足这些条件时就退出
            return -1;
        }
        // 如果没有上面的约束条件，那么当findval特别大时，mid可能会越界
        int mid = left + (right - left)*(findval - arr[left])/(arr[right]-arr[left]);
        if (findval > arr[mid]){ // 向右递归
            return insertValueSearch(arr,mid+1,right,findval);
        }else if (findval < arr[mid]){// 向左递归
            return insertValueSearch(arr,left,mid-1,findval);
        }else {
            return mid;
        }
    }
}
